package cn.edu.nju.software.puzzle;
import java.io.*;
import java.util.*;

// Assumes there are no length restrictions
// Assumes the square is a "square"; n(Row)=n(Column).
/**
 * @author smy
 *
 */
public class WordPuzzle {
    File squareFile,dictFile;
    TreeSet<String> result = new TreeSet<String>();
    String[] dict;
    char[][] square;
	public WordPuzzle(File squareFile, File dictFile) {
		this.squareFile=squareFile;
		this.dictFile=dictFile;
	}
	public Set<String> find() throws Exception {
		int total=0;
		BufferedReader dictReader=new BufferedReader(new FileReader(dictFile));
		while(dictReader.ready()){
			String s=dictReader.readLine();
			if(s.length()>=1)total++;
		}
        dict=new String[total];
	    dictReader.close();
	    dictReader=new BufferedReader(new FileReader(dictFile));
	    int limit=0;
		while(dictReader.ready()){
			String s=dictReader.readLine();
			if(s.length()>=1){dict[limit]=s;limit++;}
		}
		//Determine the number of columns of the square 
		BufferedReader squareReader=new BufferedReader(new FileReader(squareFile));
		String current=squareReader.readLine();
		current=current.trim();
		current=current.replace(" ", "");
		int columnnum=current.length();
		squareReader.close();
		//Read in the square
		BufferedReader squareReader2=new BufferedReader(new FileReader(squareFile));
	    square=new char[columnnum][columnnum];
		for (int i=0;i<columnnum;i++){
			current=squareReader2.readLine();
			current=current.trim();
			current=current.replace(" ", "");
			square[i]=current.toCharArray();
		}
		squareReader.close();
		a:
		for(int i=0;i<total;i++){
			char[] current1=dict[i].toCharArray();
			for(int j=0;j<square[0].length;j++)
				for(int k=0;k<square[0].length;k++)
					if(square[j][k]==current1[0] && (HorizontalLToR(j,k,current1,0) || HorizontalRToL(j,k,current1,0)
					   || VerticalUpToDown(j,k,current1,0) || VerticalDownToUp(j,k,current1,0) || LUTRD(j,k,current1,0)
					   || LUTRDR(j,k,current1,0) || RUTLD(j,k,current1,0) || RUTLDR(j,k,current1,0)))
					{result.add(dict[i]);continue a;}
			
		}
		return result;
	}
	//Every method below is to identify if there exists a word in the dictionary that corresponding to the strings produced by the given direction in the square 
	public boolean HorizontalLToR(int row,int column,char[]current,int curindex){
		if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
		else if(column==square.length-1)return false;
		else if(square[row][column]==current[curindex])return(HorizontalLToR(row,column+1,current,curindex+1));
		else return false;
	}
	public boolean HorizontalRToL(int row,int column,char[]current,int curindex){
        if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
        else if(column==0)return false;
        else if(square[row][column]==current[curindex])return(HorizontalRToL(row,column-1,current,curindex+1));
		else return false;
	}
	public boolean VerticalUpToDown(int row,int column,char[]current, int curindex){
		if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
		else if(row==square[row].length-1)return false;
		else if(square[row][column]==current[curindex])return(VerticalUpToDown(row+1,column,current,curindex+1));
		else return false;
	}
	public boolean VerticalDownToUp(int row, int column, char[]current, int curindex){
		if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
		else if(row==0)return false;
		else if(square[row][column]==current[curindex])return(VerticalDownToUp(row-1,column,current,curindex+1));
		else return false;
	}
	public boolean LUTRD(int row, int column, char[]current, int curindex){
		if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
		else if(row==square.length-1 || column==square.length-1)return false;
		else if(square[row][column]==current[curindex])return(LUTRD(row+1,column+1,current,curindex+1));
		else return false;
	}
	public boolean LUTRDR(int row, int column, char[]current, int curindex){
		if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
		else if(row==0 || column==0)return false;
		else if(square[row][column]==current[curindex])return(LUTRDR(row-1,column-1,current,curindex+1));
		else return false;
	}
    public boolean RUTLD(int row,int column, char[]current,int curindex){
    	if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
    	else if(row==square[row].length-1 || column==0)return false;
    	else if(square[row][column]==current[curindex])return(RUTLD(row+1,column-1,current,curindex+1));
    	else return false;
    }
    public boolean RUTLDR(int row, int column, char[]current,int curindex){
    	if(curindex==current.length-1 && square[row][column]==current[curindex])return true;
    	else if(row==0 || column==square[row].length-1)return false;
    	else if(square[row][column]==current[curindex])return(RUTLDR(row-1,column+1,current,curindex+1));
		else return false;
    }
}
